package main

import "fmt"

func main() {
	nums := []int{3, 2, 1, 5, 6, 4}
	k := 2
	v := findKthLargest(nums, k)
	fmt.Println(v)
}

// 215 数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array
func findKthLargest(nums []int, k int) int {
	// 快排
	return binarySearch(nums, 0, len(nums)-1, k)
}

func binarySearch(nums []int, start, end int, k int) int {
	l := start
	r := end
	base := nums[l]
	for l < r {
		for nums[r] >= base && r > l {
			r--
		}
		for nums[r] <= base && r > l {
			l++
		}
		if l < r {
			nums[l], nums[r] = nums[r], nums[l]
		}
	}
	nums[r], nums[start] = nums[start], nums[r]
	seek := len(nums) - k
	if r == seek {
		return nums[r]
	}
	if r > seek {
		return binarySearch(nums, start, r-1, k)
	} else {
		return binarySearch(nums, r+1, end, k)
	}
}
